package com.yileiqian.alg;

import java.util.ArrayList;
import java.util.List;

public class SieveOfEratosthenes {

	public static List<Integer> sieveOfEratoshenes(int max) {
		boolean[] flags = new boolean[max + 1];
		List<Integer> results = new ArrayList<Integer>();

		for (int i = 2; i < max; i++) {
			flags[i] = true;
		}

		int prime = 2;

		while (prime <= max) {
			results.add(prime);

			for (int i = prime * prime; i < flags.length; i += prime) {
				flags[i] = false;
			}

			prime++;
			while (prime < flags.length && !flags[prime]) {
				prime++;
			}
		}

		return results;
	}

	public static void main(String args[]) {
		List<Integer> l = sieveOfEratoshenes(46333);
		StringBuffer buffer = new StringBuffer();
		for (Integer i : l) {
			buffer.append(i);
			buffer.append(' ');
		}
		System.out.println(buffer.toString());
	}
}
